
// 1049.最后一块石头的重量II
class Solution {
public:
    int lastStoneWeightII(vector<int>& nums) {
        int n = nums.size();
        int sum = accumulate(nums.begin() , nums.end() , 0);
        
        vector<int> dp(sum / 2 + 1);
        for(int i = 1; i <= n ;i++)
            for(int j = sum/2 ; j >= nums[i - 1] ; j--)
                dp[j] = max(dp[j] , dp[j - nums[i - 1]] + nums[i - 1]);
        return abs(sum - dp[sum/2]*2);
    }
};
